Algoritmos de Ruteo de Broadcast
En broadcast Routing, la capa de red provee un servicio de entrega de paquetes enviados desde el nodo fuente hacia todos los nodos en la red.
Por otro lado, multicast Routing permite a un único nodo enviar una copia de un paquete a un subconjunto de nodos en otra red.
Dados N nodos de destino, el nodo fuente realiza N copias del paquete, direcciona cada copia a un destino distinto, y transmite todas estas a los destinos utilizando Unicast Routing. El principal problema de esta implementación es la ineficiencia, ya que, si el nodo fuente está conectado al resto de la red mediante un único enlace, entonces N copias del mismo paquete atravesaran ese único enlace.
Otro problema es cómo es obtenida la información de los receptores, ya que se asume que es conocida
In-network duplication
Una forma de implementar el broadcast es utilizando flooding, que consiste en que el nodo fuente envía una copia del paquete a todos sus vecinos. Una vez que un nodo recibe un paquete de broadcast, duplica el paquete y lo reenvía a todos sus vecinos, exceptuando a aquel del cual recibió el paquete. Sin embargo, esta aproximación tiene problemas; por ejemplo, si el grafo tiene ciclos, las copias de los paquetes de broadcast estarán en el ciclo indefinidamente. Otro problema es cuando un nodo está conectado a más de dos nodos, este creará y enviará múltiples copias del paquete de broadcast, y cada uno creará una copia de sí mismo (en otro nodo con más de dos vecinos), generando así una tormenta de broadcast, lo cual termina en múltiples paquetes generados, que no son utilizados.
Para solucionar este problema se utiliza el concepto de flooding controlado, donde la clave es que un nodo reenvía un paquete de broadcast únicamente si aún no hizo broadcast de ese paquete antes. Para implementarlo existen distintas técnicas.
- Por número de secuencia: un nodo fuente agrega su dirección al paquete, además de un número de secuencia de broadcast en el paquete de broadcast, y envía el paquete a todos sus vecinos. Luego cada nodo mantiene una lista de las direcciones y números de secuencia de cada paquete de broadcast que ya ha recibido, duplicado y reenviado. Cuando este nodo recibe un paquete, chequea en el registro si tiene una entrada para esta dirección y número de secuencia, y en caso de que si, el paquete es ignorado. En caso de que no exista, se duplica y reenvía.
- Reverse Path Forwarding (RPF): Solamente se hace el forward de un paquete si este llegó del camino más corto entre el nodo y la fuente. Por ejemplo:
Broadcast por Spanning Tree:
En primer lugar, se construye un árbol de cubrimiento. Luego los nodos reenvían copias de los paquetes solamente a través del árbol de cubrimiento construido.
Para construir el árbol de cubrimiento, en primer lugar, se toma un nodo central. Luego cada nodo envía un mensaje unicast de join al nodo central. El mensaje será reenviado hasta que llega a un nodo que ya pertenece al árbol de cubrimiento.
Broadcast vs flooding
Ambos mecanismos cumplen la misma función: enviar una copia de un mensaje a todos los nodos de una red. En el caso de broadcast típicamente se asume un medio compartido (por ejemplo un dominio de broadcast ethernet), donde el origen de la comunicación envía un mensaje a una dirección especial que representa a todos los nodos. En redes con topologías arbitrarias, el envío de un mensaje a todos los nodos se puede implementar mediante flooding.
Ethernet 802.3 tiene la dirección FF:FF:FF:FF:FF:FF definida como dirección de broadcast.
OSPF utiliza flooding para el envío de información de estado-enlace entre routers; en este caso se utiliza como destino una dirección de multicast que representa a todos los routers.
Multicast
La idea es encontrar un árbol o árboles conectando routers teniendo miembros de un grupo local de multicast.
- Tree: no todos los caminos entre routers son usados.
- Source-based: diferente árbol desde cada emisor a receptor.
- Shared-tree: el mismo árbol utilizado por todos los miembros del grupo.
Aproximaciones para la construcción de árboles de multicast
- Source-based tree: un árbol por fuente.
- Shortest Path trees.
- Reverse Path Forwarding.
- Group-shared tree: el grupo usa un árbol.
- Minimal Spanning (Steiner).
- Center-based trees.
